package com.javaDemo.ti;

/**
 * @ClassName: FindPeakElement
 * @Description: 查找先升序后降序数组中的最大元素
 * 给定一个整型数组，数组元素不重复，数组元素先升序后降序，
 * 例如：1,3,5,7,9,8,6,4,2，请写一个函数找出数组最大的元素。
 */
public class FindPeakElement {

    /**
     * 查找先升序后降序数组中的最大元素
     * 算法思想：二分查找
     * 时间复杂度：O(log n)
     * 空间复杂度：O(1)
     *
     * @param nums 先升序后降序的数组
     * @return 数组中的最大元素
     */
    public static int findPeakElement(int[] nums) {
        // 参数校验
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("数组不能为空");
        }
        
        // 特殊情况处理：数组只有一个元素
        if (nums.length == 1) {
            return nums[0];
        }
        
        // 特殊情况处理：如果数组是单调递增的，最后一个元素就是最大值
        if (nums[nums.length - 1] > nums[nums.length - 2]) {
            return nums[nums.length - 1];
        }
        
        // 特殊情况处理：如果数组是单调递减的，第一个元素就是最大值
        if (nums[0] > nums[1]) {
            return nums[0];
        }
        
        // 二分查找
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            // 如果中间元素比两边都大，那么它就是最大值
            if ((mid == 0 || nums[mid] > nums[mid - 1]) && 
                (mid == nums.length - 1 || nums[mid] > nums[mid + 1])) {
                return nums[mid];
            }
            
            // 如果中间元素比右边小，说明最大值在左半部分（包括中间元素）
            if (mid < nums.length - 1 && nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else { // 否则，最大值在右半部分
                right = mid - 1;
            }
        }
        
        // 理论上不会执行到这里，因为数组中一定有最大值
        return -1;
    }

    /**
     * 主方法，用于测试
     * 
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        // 测试用例1：标准的先升序后降序数组
        int[] nums1 = {1, 3, 5, 7, 9, 8, 6, 4, 2};
        System.out.println("测试用例1：标准的先升序后降序数组");
        System.out.println("数组：[1, 3, 5, 7, 9, 8, 6, 4, 2]");
        System.out.println("最大元素：" + findPeakElement(nums1));
        System.out.println();
        
        // 测试用例2：只有一个元素的数组
        int[] nums2 = {5};
        System.out.println("测试用例2：只有一个元素的数组");
        System.out.println("数组：[5]");
        System.out.println("最大元素：" + findPeakElement(nums2));
        System.out.println();
        
        // 测试用例3：单调递增的数组
        int[] nums3 = {1, 2, 3, 4, 5};
        System.out.println("测试用例3：单调递增的数组");
        System.out.println("数组：[1, 2, 3, 4, 5]");
        System.out.println("最大元素：" + findPeakElement(nums3));
        System.out.println();
        
        // 测试用例4：单调递减的数组
        int[] nums4 = {5, 4, 3, 2, 1};
        System.out.println("测试用例4：单调递减的数组");
        System.out.println("数组：[5, 4, 3, 2, 1]");
        System.out.println("最大元素：" + findPeakElement(nums4));
        System.out.println();
        
        // 测试用例5：最大值在中间的数组
        int[] nums5 = {1, 2, 10, 8, 7, 6, 5};
        System.out.println("测试用例5：最大值在中间的数组");
        System.out.println("数组：[1, 2, 10, 8, 7, 6, 5]");
        System.out.println("最大元素：" + findPeakElement(nums5));
    }
}